'''
Created on May 22, 2009

@author: Roni
'''

class cliqueFinder(object):
    '''
    classdocs
    '''

    def __init__(self):
        '''
        Constructor
        '''
    
    def setup(self,searched_graph):
        self.graph = searched_graph
    
    def find_clique(self,k,nodes):
        ''' Returns a list with a k-clique from the given nodes,
        is such exists, or None if such does not exist
        '''
        # Stop condition
        if k==1:
            if len(nodes)>0:
                return [nodes[0]]
            else:
                return None
            
        # Recursive call
        relevant_nodes=set(nodes)
        while len(relevant_nodes)>0:
            node = relevant_nodes.pop()
            neighbors = self.graph.neighbors(node)
            #potential_members=neighbors.intersection(nodes)
            potential_members=filter(lambda x:x in neighbors,relevant_nodes)
            
            if len(potential_members)>=k-1: # If can grow to a k-clique, continue
                partial_clique = self.find_clique(k-1, potential_members)
                if partial_clique is not None:
                    partial_clique.extend([node])
                    return  partial_clique
        return None
    
    
    def has_clique(self,k,nodes):
        '''
        Checks if the given nodes contain a k-clique
        k - Size of the desired clique
        nodes - list of nodes from the searched graph in which to search
        '''
        # Stop condition
        if k==1:
            if len(nodes)>0:
                return True
            else:
                return False
            
        # Recursive call
        relevant_nodes=set(nodes)
        while len(relevant_nodes)>0:
            node = relevant_nodes.pop()
            neighbors = self.graph.neighbors(node)
            #potential_members=neighbors.intersection(nodes)
            potential_members=filter(lambda x:x in neighbors,relevant_nodes)
            
            if len(potential_members)>=k-1: # If can grow to a k-clique, continue
                if self.has_clique(k-1,potential_members):
                    return True
        return False
    
        
            